package cn.kent;

/**
 * 寻找最长回文字符串
 * 示例 1：
 * <p>
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 * <p>
 * 输入：s = "cbbd"
 * 输出："bb"
 * 示例 3：
 * <p>
 * 输入：s = "a"
 * 输出："a"
 * 示例 4：
 * <p>
 * 输入：s = "ac"
 * 输出："a"
 */
public class LongestPalindrome {
    public static void main(String[] args) {
        // String s = "babad";
        // String s = "aaaaa";
        // String s = "bb";
        // String s = "aacabdkacaa";
        String s = "tattarrattat"; // "tattarrattat"
        String s1 = longestPalindrome2(s);
        System.out.println("最长回文字符串为：" + s1);
    }


    /**
     * 第二版
     * 三种情况： bb   cbabc  tattarrattat  这三种情况都符合要求
     */
    public static String longestPalindrome2(String s) {
        // 1. 判空
        if (s == null) {
            return null;
        }

        // 2. 从左向右滑动
        int left = 0;
        int right = 0;
        // 外层循环，开始滑动
        for (int i = 0; i < s.length() - 1; i++) {
            int x = 1;
            // 中间值的左右判断
            while (i - x >= 0 && i + x < s.length()) {
                if (s.charAt(i - x) == s.charAt(i + x)) { // aba
                    if ((right - left) < (2 * x)) {
                        left = i - x;
                        right = i + x;
                    }
                    x++;
                } else {
                    break;
                }
            }

            x = 1;
            // abba -> abba 判断
            // 判断是否和后面一位相等，
            if (i + x < s.length() && s.charAt(i) == s.charAt(i + x)) {
                x++;
                while (i - x + 1 >= 0 && i + x < s.length()) {
                    if (s.charAt(i - x + 1) == s.charAt(i + x)) {
                        if ((right - left) < (i + x - (i - x + 1))) {
                            left = i - x + 1;
                            right = i + x;
                        }
                        x++;
                    } else {
                        break;
                    }
                }
            }

            x = 1;
            // 向后判断
            while (i + x < s.length()) {
                if (s.charAt(i) == s.charAt(i + x)) {
                    if ((right - left) < x) {
                        left = i;
                        right = i + x;
                    }
                    x++;
                } else {
                    break;
                }
            }
        }

        return s.substring(left, right + 1);
    }

    /**
     * 思路：
     * 滑动，从左向右滑动判断。
     * 记录索引和长度，最后截取
     */
    @SuppressWarnings({"all"})
    public static String longestPalindrome(String s) {
        // 1. 判空
        if (s == null) {
            return null;
        }
        String res = String.valueOf(s.charAt(0));

        int left = 0;
        int right = 0;
        int len = 0;
        // 2. 滑动
        for (int i = 1; i < s.length() - 1; i++) { // 外层循环： 负责向后滑动

            int x = 1;
            String substring = "";
            boolean bool = true;
            while (bool) {
                for (int j = 0; j < i; j++) { // 内层循环，负责匹配判断
                    // 两种情况： 先前后比对，匹配完后 -> 再向后匹配相同字符
                    if (s.charAt(i - x) == s.charAt(i + x) && i - x >= 0 && i + x + 1 <= s.length()) { // 前后匹配
                        substring = s.substring(i - x, i + x + 1);
                    } else {
                        bool = false;
                    }
                    x++;
                }
                bool = false;
            }
            bool = true;
            while (bool) {
                for (int j = 0; j < i; j++) { // 内层循环，负责匹配判断
                    if (s.charAt(i + x) == s.charAt(i)) { // 向后匹配相同值
                        substring = s.substring(i, i + x + 1).length() > substring.length() ? s.substring(i, i + x + 1) : substring;
                    } else {
                        bool = false;
                    }
                    x++;
                }
                bool = false;
            }
            res = substring.length() > res.length() ? substring : res;

        }

        return res;
    }
}
